class MySingleLinkedList {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;//代表链表的头结点

    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void display(ListNode newHead) {
        ListNode cur = newHead;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void addFirst(int val) {
        ListNode node = new ListNode(val);
        node.next = head;
        head = node;
    }
}

public class Demo2_5 {
    //合并两个有序链表
    //将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    public static MySingleLinkedList.ListNode mergeTwoLists(MySingleLinkedList.ListNode headA,
                                                            MySingleLinkedList.ListNode headB) {
        MySingleLinkedList.ListNode pos = new MySingleLinkedList.ListNode(-1);
        MySingleLinkedList.ListNode tmp = pos;
        while (headA != null && headB != null) {
            if (headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            } else {
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }
        }
        if (headA == null) {
            tmp.next = headB;
        }
        if (headB == null) {
            tmp.next = headA;
        }
        return pos.next;
    }

    public static void main(String[] args) {
        MySingleLinkedList msl1 = new MySingleLinkedList();
        msl1.addFirst(4);
        msl1.addFirst(2);
        msl1.addFirst(1);
        MySingleLinkedList msl2 = new MySingleLinkedList();
        msl2.addFirst(4);
        msl2.addFirst(3);
        msl2.addFirst(1);
        MySingleLinkedList.ListNode newH = mergeTwoLists(msl1.head, msl2.head);
        msl1.display(newH);
    }
}
